Petit théorème de Fermat (forme forte)

Petit théorème de Fermat (forme forte)

Si \(p \in \mathcal{P}\) , alors pour tout \(n \in \mathbb{Z}\) tel que \(p\) ne divise pas \(n\) , on a :  \(n^{p-1} \equiv 1 \ [p]\) .

Démonstration

Soit \(p \in \mathcal{P}\) et \(n \in \mathbb{Z}\) tel   que \(p\) ne divise pas \(n\) .
On considère les nombres \(n\) , \(2n\) , \(3n\) , ..., \((p-1)n\) , c'est-à-dire \(kn\) pour \(k \in \left\lbrace 1;...;p-1 \right\rbrace\) .

Pour tout \(k \in \left\lbrace 1;...;p-1 \right\rbrace\) , on note \(r_k\) le reste dans la division euclidienne de \(kn\) par \(p\) ,
c'est-à-dire  \(kn=pq_k+r_k\)  avec  \(q_k \in \mathbb{Z}\)  et  \(0 \leqslant r_k.

Observation 1 : pour tout \(k \in \left\lbrace 1;...;p-1 \right\rbrace\) , on a \(r_k \in \left\lbrace 1;...;p-1 \right\rbrace\) .
En effet, soit \(k \in \left\lbrace 1;...;p-1 \right\rbrace\) . On sait déjà que \(r_k \in \left\lbrace 0;...;p-1 \right\rbrace\) .
De plus, \(p\) ne divise pas \(k\) (car \(0) et \(p\) ne divise pas \(n\) , donc \(p\) ne divise pas \(kn\) .
Or \(kn=pq_k+r_k\) , donc \(r_k \neq 0\) .

Observation 2 : pour tous \(k\) , \(k' \in \left\lbrace 1;...;p-1 \right\rbrace\) , si \(k \neq k'\) , alors \(r_k \neq r_{k'}\) .
En effet, soit \(k\) , \(k' \in \left\lbrace 1;...;p-1 \right\rbrace\) tels que \(k.
Ainsi, \(k'-k \in \left\lbrace 1;...;p-1 \right\rbrace\) .
Par suite, \(p\) ne divise pas \(k'-k\) et \(p\) ne divise pas \(n\) , donc \(p\) ne divise pas  \(n(k'-k)=nk'-nk=pq_{k'}+r_{k'}-(pq_k+r_k)=p(q_{k'}-q_k)+r_{k'}-r_k\)  
et donc \(r_{k'}-r_k \neq 0\) , c'est-à-dire \(r_k \neq r_{k'}\) .

D'après les deux observations précédentes, l'ensemble \(\left\lbrace r_1 \ ; r_2 \ ; ... \ ; r_{p-1} \right\rbrace\) est formé de \((p-1)\) entiers tous distincts, et cet ensemble est inclus dans  \(\left\lbrace 1;...;p-1 \right\rbrace\) .
Par conséquent, cet ensemble est exactement \(\left\lbrace 1;...;p-1 \right\rbrace\) (dans un ordre quelconque).

On en déduit que  \(r_1r_2...r_{p-1}=1 \times 2 \times ... \times (p-1)=(p-1)!\) .

Pour tout \(k \in \left\lbrace 1;...;p-1 \right\rbrace\) , on a \(kn=pq_k+r_k\) donc \(kn \equiv r_k \ [p]\) .

Par produit,
\(\begin{align*}1n \times 2n \times ... \times (p-1)n \equiv r_1r_2...r_{p-1} \ [p]& \ \ \Longleftrightarrow \ \ (p-1)!n^{p-1} \equiv (p-1)! \ [p]\\ & \ \ \Longleftrightarrow \ \  (p-1)!(n^{p-1}-1) \equiv 0 \ [p]\end{align*}\)  
donc \(p\) divise \((p-1)!(n^{p-1}-1)\) .

Comme \(p\) et \((p-1)!\) sont premiers entre eux, on en déduit grâce au théorème de Gauss que \(p\) divise \(n^{p-1}-1\) , c'est-à-dire \(n^{p-1}-1 \equiv 0 \ [p]\) , et donc \(n^{p-1} \equiv 1 \ [p]\) .